1. Field of the Invention
The present invention relates to a technique for Fast Fourier Transform (FFT) process.
2. Description of Related Art
As the bandwidth of communications increases, complex signal processing has been required on a greater amount of information. Such examples include the OFDM (Orthogonal Frequency Division Multiplexing) and the FDE (Frequency Domain Equalization), and the realization of these requires a high throughput FFT that utilizes hardware.
Hardware implementation of a high throughput FFT requires a large amount of hardware resources. ADC and DAC are utilized for the input and output of the FFT, which increases the operational speed associated with broadening bandwidths. Thus, the ENoB (Effective number of bits) of ADC and DAC is limited. The order, throughput, and ENoB value of ADC/DAC required for a currently desired FFT are listed below.                512-point (order N=512) FFT for IEEE802.15.3c (mmWave)        2.5G symbol per second        8-bit ADC/DAC for 2.5G sps        
In order to fulfill the above described requirements and to enable the FFT implementation with a minimized scale of circuit, some contrivance is needed such as using radix-8 which is higher than conventionally used radixes such as radix-2 and radix-4 and further implementing its operation based on a fixed point decimal (j bits, j is a natural number). However, a fixed-point FFT has a problem in that roundoff error during the operation increases.
In WO 2009/142563 A1 “METHOD FOR MOVING QUANTIZATION NOISE INTRODUCED IN FIXED-POINT CALCULATION OF FAST FOURIER TRANSFORMS” (International Patent Publication), which in the background considers the use of a fixed-point FFT for the purpose of a low-power and low cost implementation, a quantization error can occur. Such quantization error locally increases depending on the rotation within the FFT, and such an increased error is not likely to act as a noise source for the code to be transmitted/received upon occurring in the cyclic prefix portion of the OFDM in the time domain, but when on the contrary, the error is superposed on other portions, it will act as a noise source
In WO 2009/142563 A1 “METHOD FOR MOVING QUANTIZATION NOISE INTRODUCED IN FIXED-POINT CALCULATION OF FAST FOURIER TRANSFORMS” (International Patent Publication), in the frequency domain, when such error is superposed on the DC component, the error will increase, but when it is on the subcarrier side, the effect of the error will be small. Accordingly, there is disclosed a technique for reducing the effect of error on the code to be transmitted/received by shifting symbols after IFFT to displace the location where quantization error occurs.
In contrast, the present invention is a method for decreasing the quantization error within FFT and IFFT, and therefore is different from the technique of WO 2009/142563 A1 “METHOD FOR MOVING QUANTIZATION NOISE INTRODUCED IN FIXED-POINT CALCULATION OF FAST FOURIER TRANSFORMS” (International Patent Publication).
In U.S. Pat. No. 2005/0289207 A1 “FAST FOURIER TRANSFORM PROCESSOR, DYNAMIC SCALING METHOD AND FAST FOURIER TRANSFORM WITH RADIX-8 ALGORITHM” (US Patent Publication), in its background, as the order of FFT increases, the SQNR (signal to quantization noise ratio) decreases thereby causing an adverse effect. Reducing the adverse effect will require a longer word length as the number of operation bits within the FFT in the case of a higher order FFT. Moreover, in an FFT processor, a block-floating point is used in which effective digits of values of multiple adjacent input data are implemented so as to provide a common effective digit between adjacent values such that the entire multiple adjacent data have one effective digit.
U.S. Pat. No. 2005/0289207 A1 “FAST FOURIER TRANSFORM PROCESSOR, DYNAMIC SCALING METHOD AND FAST FOURIER TRANSFORM WITH RADIX-8 ALGORITHM” (US Patent Publication) discloses a method for performing a pipeline operating by dividing radix-8 into 3 stages (substantially expanding it into radix-2) to decrease the complex multiplication circuit by use of a block-floating point. Although this will reduce the amount of circuit, the latency required for operation increases by three times. Further, it discloses a method for scheduling so as to reduce the number of multiplication (3rd stage) by using a buffer to cash values called as a prefetch buffer, so that the normalization of block-floating is effectively implemented by making use of the prefetch buffer.
However, it has no technical idea corresponding to that of the present invention which preserves a 45-degree rotation portion in radix-8.
U.S. Pat. No. 2004/0111227 A1 “METHOD AND SYSTEM FOR FIXED POINT FAST FOURIER TRANSFORM WITH IMPROVED SNR” (US Patent Publication) discloses a method for scaling the output value so as to have a maximum value within a range not to overflow in each internal butterfly operation of FFT. It is considered to be relatively common method; but it relates to a different portion from that of the method for the present invention.
U.S. Pat. No. 2006/0282764 A1 “HIGH-THROUGHPUT PIPELINED FFT PROCESSOR” (US Patent Publication) discloses a hardware architecture for performing the operation of 128-bit FFT for UWB, the architecture having realized a butterfly-2 unit and radix-8 by dividing it into 3 stages (substantially combination of radix-2). It is a disclosure of a very particular architecture, and does not include the technical idea of the present invention.
WO 2007/115329 A2 “FFT ARCHITECTURE AND METHOD” (International Patent Publication) (National Publication (in Japanese) after transition to National Phase in Japan, National Publication of International Patent Application No. 2009-535678 “ARCHITECTURE AND METHOD FOR PIPELINE FFT”) discloses an architecture and its operation of a pipeline-type FFT incorporating a butterfly operation of radix-2. That is quite different from the feature relating to the radix-8 of the present invention.
Cooley, James W., and John W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” Math. Comput. 19, 297-301, 1965. relates to a representative FFT algorithm known as the Cooley-Tukey FFT.
It is an object of the present invention to reduce roundoff errors in FFT operation.